<?php
declare(strict_types=1);

namespace assist;

/**
 * Class Alg
 * @package assist
 */
class Alg
{

    /**
     *
     *
     * @param array $sets
     * @return array|mixed
     */
    public static function CartesianProduct(array $sets = [])
    {

        // 保存结果
        $result = [];

        // 循环遍历集合数据
        for ($i = 0, $count = count($sets); $i < $count - 1; $i++) {

            // 初始化
            if ($i == 0) $result = $sets[$i];

            // 保存临时数据
            $tmp = [];

            // 结果与下一个集合计算笛卡尔积
            foreach ($result as $res) {
                foreach ($sets[$i + 1] as $set) {
                    $tmp[] = $res . $set;
                }
            }
            // 将笛卡尔积写入结果
            $result = $tmp;
        }
        return $result;
    }

    /**
     * 阶乘
     *
     * @param $n
     * @return float|int
     */
    public static function factorial(int $n)
    {
        return array_product(range(1, $n));
    }


    /**
     * 排列数
     *
     * @param $n
     * @param $m
     * @return float|int
     */
    public static function rangeMentNumber(int $n, int $m)
    {
        return self::factorial($n) / self::factorial($n - $m);
    }

    /**
     * 组合数
     *
     * @param $n
     * @param $m
     * @return float|int
     */
    public static function combinationNumber(int $n, int $m)
    {
        return self::rangeMentNumber($n, $m) / self::factorial($m);
    }


    /**
     * 排列
     *
     * @param array $basic
     * @param int $digit
     * @return array
     */
    public static function rangeMent(array $basic = [], int $digit = 1)
    {
        $result = [];

        $n = count($basic);
        if ($digit <= 0 || $digit > $n) return $result;

        for ($i = 0; $i < $n; $i++) {
            $b = $basic;
            $t = array_splice($b, $i, 1);
            if ($digit == 1) {
                $result[] = $t;
            } else {
                $c = self::rangeMent($b, $digit - 1);
                foreach ($c as $v) {
                    $result[] = array_merge($t, $v);
                }
            }
        }

        return $result;
    }


    /**
     * 组合
     *
     * @param array $basic
     * @param int $digit
     * @return array
     */
    public static function combination(array $basic = [], int $digit = 1)
    {
        $result = [];

        $n = count($basic);
        if ($digit <= 0 || $digit > $n) return $result;

        for ($i = 0; $i < $n; $i++) {
            $t = [$basic[$i]];
            if ($digit == 1) {
                $result[] = $t;
            } else {
                $b = array_slice($basic, $i + 1);
                $c = self::combination($b, $digit - 1);
                foreach ($c as $v) {
                    $result[] = array_merge($t, $v);
                }
            }
        }
        return $result;
    }

}
